#include "StdAfx.h"
#include "DPTest.h"


DPTest::DPTest(void)
{
}


DPTest::~DPTest(void)
{
}

void LCS(char* A, char* B, int aLen, int bLen)
{
	//Should check input parameters firstly, ignored
	vector<vector<int>> lcs(aLen+1, vector<int>(bLen+1, 0));

	for( int i = 0; i < aLen; ++i)
	{
		for(int j = 0; j < bLen; ++j)
		{
			if( A[i] == B[j])
			{
				lcs[i+1][j+1] = lcs[i][j] + 1;			
			}
			else if ( lcs[i][j+1] > lcs[i+1][j])
			{
				lcs[i+1][j+1] = lcs[i][j+1];
			}
			else 
			{
				lcs[i+1][j+1] = lcs[i+1][j];
			}
			cout << lcs[i+1][j+1] << ",";
		}
		cout << endl;
	}

	//Now print the LCS
	string l;
	while( aLen >= 1 && bLen >= 1)
	{
		if( lcs[aLen][bLen] == lcs[aLen-1][bLen] )
		{
			aLen--;  //Go up;
		}
		else if( lcs[aLen][bLen] == lcs[aLen][bLen-1] )
		{
			bLen--;  //Go left
		}
		else if( lcs[aLen][bLen-1] == lcs[aLen-1][bLen] )
		{
			l = A[aLen-1] + l; 
			aLen--;  //Go leftup
			bLen--; 
		}
		else
		{
			aLen--;  //Go leftup
			bLen--; 
		}
	}
	cout << "The longest common string = " << l << endl;
}

TEST_F(DPTest, LCS)
{
	char* A = "BDCABA";
	char* B = "ABCBDAB";

	LCS(B, A, 7, 6);
	LCS(A, B, 6, 7);
}

TEST_F(DPTest, LCS2)
{
	char* A = "BDDABA";
	char* B = "ABCBDAB";

	LCS(B, A, 7, 6);
	LCS(A, B, 6, 7);
}

TEST_F(DPTest, LCS3)
{
	char* A = "DDAAAA";
	char* B = "CCCCCCC";

	LCS(B, A, 7, 6);
	LCS(A, B, 6, 7);
}